#89信道分配
# R = int(input())
# N = list(map(int,input().split()))
# D = int(input())
# def calc_sub(bin1):
#     ans = 0
#     for i in range(len(bin1)):
#         ans += bin1[i] * (1 << i)
#         return ans
#
# def binary_sub(minuend,subtrahend):
#     #进行减法，从高位开始
#     i = len(minuend) - 1
#     while i>= 0:
#         if minuend[i] >= subtrahend[i]:
#             minuend[i] -= subtrahend[i]
#         else:
#             #两种策略向高/低位借
#             #看minuend[0,i]低位部分是否能够承载subtrahend[0,i]低位部分
#             if calc_sub(minuend[0:i+1]) <calc_sub(subtrahend[0:i+1]):
#                 #低位不够借
#                 j = i + 1
#                 while j < len(minuend):
#                     if minuend[j] > 0:
#                         minuend[j] -= 1
#                         return True
#                     else:
#                         j+= 1
#                 return False
#             else:
#                 #可以向低位借，负数表示欠债
#                 minuend[i] -= subtrahend[i]
#                 #欠债转移到低阶位上
#                 minuend[i-1]  += minuend[i] << 1
#                 minuend[i] = 0
#         i-= 1
#     return True
# subtrahend = list(map(int,str(bin(D))[2:]))
# subtrahend.reverse()
# #count 记录 N能承载几个D
# count = 0
# #N中高阶信道的单个信道就能满足D，因此这些高阶信道有几个，既能承载几个D
# for i in range(len(subtrahend),R+1):
#     count += N[i]
#
# #0 ~ subtrahend.length -1 阶的信道需要组合起来承载一个D
# minuend = N[0:len(subtrahend)]
# while len(minuend) < len(subtrahend):
#     minuend.append(0)
#
# #进行二进制减法
# while binary_sub(minuend,subtrahend):
#     count+=1
# print(count)
import math
import shlex
import sys
from importlib.metadata import requires

#88狙击战
# import sys
# steps = list(map(int,input()[1:-1].split(',')))
# count = int(input())
#
# class Step:
#     def __init__(self,val,idx):
#         self.val = val
#         self.idx = idx
#
# n = len(steps)
# newSteps = [Step(steps[i],i) for i in range(n)]
# newSteps.sort(key = lambda x:(x.val,x.idx))
# minStepIdxSum = sys.maxsize
# ans = ''
# for i in range(n):
#     #剪枝优化
#     if newSteps[i].val > 0 and 0 < count < newSteps[i].val:
#         break
#     if i > 0 and newSteps[i].val == newSteps[i-1].val:
#         continue
#     l = i + 1
#     r = n - 1
#     while l < r:
#         threshold = (count - newSteps[i].val) / 2
#         if newSteps[l].val > threshold or  newSteps[r].val < threshold:
#             break
#         stepValSum = newSteps[i].val + newSteps[l].val + newSteps[r].val
#         if stepValSum < count:
#             l += 1
#         elif stepValSum > count:
#             r-= 1
#         else:
#             while l < r- 1 and newSteps[r].val == newSteps[r-1].val:
#                 r -= 1
#             stepIdxSum = newSteps[i].idx + newSteps[l].idx + newSteps[r].idx
#             if stepIdxSum < minStepIdxSum:
#                 minStepIdxSum = stepIdxSum
#                 arr = [newSteps[i],newSteps[l],newSteps[r]]
#                 arr.sort(key=lambda x:x.idx)
#                 ans = '[' + ','.join(map(lambda x:str(x.val),arr)) + ']'
#             while l + 1 < r and newSteps[l].val == newSteps[l+1].val:
#                 l+=1
#             l+=1
#             r-=1
# print(ans)

#87环形字符串最长子串二
# s = input()
# status = 0b000
# dic = [[] for _ in range(8)]
# dic[0].append(-1)
#
# maxLen = 0
# for i in range(2 * len(s)):
#     #第二轮时，i >= s.length,此时i需要对s.length取余，避免后面越界
#     c = s[i % len(s)]
#     if c == 'l':
#         status ^= 0b100
#     elif c == 'o':
#         status ^= 0b010
#     elif c == 'x':
#         status ^= 0b001
#
#     if i < len(s):
#         #第一轮左闭右开，记录状态出现过的位置
#         dic[status].append(i)
#
#     while len(dic[status]) > 0:
#         #status状态最早出现的位置
#         earliest = dic[status][0]
#         #i时当前位置和earliest位置状态相同
#         if i - earliest > len(s):
#             #如果(earliest,i]范围长度超过s串长度，说明earliest左越界，尝试更大一点的earliest
#             dic[status].pop(0)
#         else:
#             maxLen = max(maxLen,i-earliest)
#             break
#
# print(maxLen)

#86取出尽量少的球
# SUM,N = map(int,input().split())
# bucketBallNums = list(map(int,input().split()))
#
# def check(maxCapacity):
#     remain = 0
#     for i in range(N):
#         remain+= min(bucketBallNums[i],maxCapacity)
#     return remain <= SUM
#
# if sum(bucketBallNums) < SUM:
#     print('[]')
# low = 0
# high = max(bucketBallNums)
# limit = 0
# while low <= high:
#     mid = (low+high) // 2
#     if check(mid):
#         limit = mid
#         low = mid + 1
#     else:
#         high = mid -1
#
# res = list(map(lambda num:str(num-min(num,limit)),bucketBallNums))
# print(f'[{','.join(res)}]')

#85贪心歌手
# import heapq
# t,n = map(int,input().split())
# roadCost =  sum(map(int,input().split()))
# mds = [list(map(int,input().split())) for _ in range(n)]
# def solution():
#     remain = t - roadCost
#     if remain <= 0:
#         return 0
#     pq = []
#     for m,d in mds:
#         while m > 0:
#             #只有remain天可以赚钱，超出时间不能赚钱，比较超出的时间赚的钱m，和前面时间中赚的最少的钱pq[0]
#             if len(pq) >= remain:
#                 #pq[0]只可能是某个城市停留的最后一天赚的钱
#                 if m > pq[0]:
#                     #当前城市当天赚的钱m比前面某天里赚的最少的多，那就节约出来
#                     heapq.heappop(pq)
#                 else:
#                     break
#             heapq.heappush(pq,m)
#
#             m -= d
#     return sum(pq)

#84两个字符串间最短路径
# A,B = input().split()
# m,n = len(B),len(A)
# def solution():
#     #preRow第一行上各点到0,0点的最短距离
#     preRow = [i for i in range(n+1)]
#     #记录第二行上各点到0,0点的最短距离
#     curRow = [0] * (n+1)
#     for i in range(1,m+1):
#         # i,0到0,0点的最短距离
#         curRow[0] = i
#         for j in range(1,n+1):
#             if A[j-1] == B[i-1]:
#                 curRow[j] = preRow[j-1] + 1
#             else:
#                 curRow[j] = min(preRow[j],curRow[j-1])+1
#         for j in range(n+1):
#             preRow[j] = curRow[j]
#     return curRow[n]

#82最小覆盖矩阵
# import sys
#
# # 输入获取
# n, m = map(int, input().split())  # 矩阵 [行数, 列数]
# matrix = [list(map(int, input().split())) for _ in range(n)]  # 矩阵
# k = int(input())  # 目标数组长度
# nums = list(map(int, input().split()))  # 目标数组
# cnts = {}
# for num in nums:
#     cnts.setdefault(num,0)
#     cnts[num] += 1
# def solution():
#     total = k
#     minLen = sys.maxsize
#     l = 0
#     r = 0
#     while r < m:
#         for i in range(n):
#             numR = matrix[i][r]
#             if numR in cnts:
#                 if cnts[numR] > 0:
#                     total -= 1
#                 cnts[numR] -= 1
#         while total == 0:
#             minLen = min(minLen,r-l+1)
#             for i in range(n):
#                 numL = matrix[i][l]
#                 if numL in cnts:
#                     if cnts[numL] >= 0:
#                         total += 1
#                     cnts[numL] += 1
#             l += 1
#         r += 1
#     return (-1 if minLen == sys.maxsize else minLen)

#攀登者2
# heights = list(map(int,input().split(',')))
# strength = int(input())
# def climb(idxs,direction):
#     j = 0
#     while j < len(heights) and heights[j] != 0:
#         j += 1
#     cost = 0
#     for i in range(j+1,len(heights)):
#         if heights[i] == 0:
#             cost = 0
#             continue
#         diff = heights[i] - heights[i-1]
#         if diff > 0:
#             cost += diff * 3
#             if i + 1 >= len(heights) or heights[i] > heights[i+1]:
#                 if cost < strength:
#                     if direction:
#                         idxs.add(i)
#                     else:
#                         idxs.add(len(heights)-i-1)
#         elif diff < 0:
#             cost -= diff * 3
# def solution():
#     idxs = set()
#     climb(idxs,True)
#     heights.reverse()
#     climb(idxs,False)
#     return len(idxs)


# 80 实心不规则图形周长
# n = int(input())
# lines = [list(map(int, input().split())) for _ in range(n)]
# def solution():
#     # 记录每个图形的边长
#     ans = []
#
#     # 定义一个100*100的矩阵
#     matrix = [[0] * 100 for _ in range(100)]
#
#     # 向100*100的矩阵中填充数字
#     for line in lines:
#         # 每行第一个数是矩阵单元格填充的数字
#         num = line[0]
#
#         # 后续每两个一组，表示填充该数字的单元格坐标
#         for i in range(1, len(line), 2):
#             x = line[i]
#             y = line[i + 1]
#             matrix[x][y] = num  # 填充数字
#
#     offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))
#
#     # 遍历每个图形的坐标
#     for line in lines:
#         num = line[0]
#         p = 0  # 周长
#
#         for i in range(1, len(line), 2):
#             x = line[i]
#             y = line[i + 1]
#
#             # 遍历图形中元素的上下左右
#             for offsetX, offsetY in offsets:
#                 newX = x + offsetX
#                 newY = y + offsetY
#
#                 # 则如果图形元素的上或下或左或右不是图形值，那么当前图形的边长+1
#                 # 如果图形元素的上或下或左或右越界了，则当前图形边长也+1
#                 if newX < 0 or newX >= 100 or newY < 0 or newY >= 100 or matrix[newX][newY] != num:
#                     p += 1
#
#         ans.append(p)
#
#     return " ".join(map(str, ans))

#79 服务失效判断
# relations = [s.split('-') for s in input().split(',')]
# breakdowns = input().split(',')
# def remove(next,s):
#     if next.get(s) is not None:
#         need_remove = next[s]
#         del next[s]
#         for ss in need_remove:
#             remove(next,ss)
# def solution():
#     next = {}
#     first = {}
#     i = 0
#     for ch,fa in relations:
#         next.setdefault(ch,set())
#         next.setdefault(fa,set())
#         next[fa].add(ch)
#         if first.get(ch) is None:
#             first[ch] = i
#             i+= 1
#         if first.get(fa) is None:
#             first[fa] = i
#             i+= 1
#     for s in breakdowns:
#         remove(next,s)
#     res = list(next.keys())
#     if len(res) == 0:
#         return ','
#     else:
#         res.sort(key = lambda x:first[x])
#         return ','.join(res)

#78Linux发行版的数量
# class UnionFindSet:
#     def __init__(self,n):
#         self.fa = [idx for idx in range(n)]
#     def find(self,x):
#         if x!= self.fa[x]:
#             self.fa[x] = self.find(self.fa[x])
#             return self.fa[x]
#         return x
#     def union(self,x,y):
#         x_fa = self.find(x)
#         y_fa = self.find(y)
#         if x_fa != y_fa:
#             self.fa[y] = x_fa
# def solution():
#     n = int(input())
#     matrix = []
#     for i in range(n):
#         matrix.append(list(map(int,input().split())))
#     ufs = UnionFindSet(n)
#     for i in range(n):
#         for j in range(i+1,n):
#             if matrix[i][j] == 1:
#                 ufs.union(i,j)
#     connected = {}
#     for i in range(n):
#         fa = ufs.find(ufs.fa[i])
#         connected[fa] = connected.get(fa,0)+1
#     return  max(connected.values())

#76不含101的数字
# def dfs(p,limit,f,arr,pre,prepre):
#     if p == len(arr):
#         return 1
#     if not limit and f[p][pre][prepre] > 0:
#         return f[p][pre][prepre]
#     maxV = arr[p] if limit else 1
#     count = 0
#     for i in range(maxV + 1):
#         if i == 1 and pre == 0 and prepre == 1:
#             continue
#         count += dfs(p+1,limit and i == maxV,f,arr,i,pre)
#     if not limit:
#         f[p][pre][prepre] = count
#     return count
# def digitSearch(num):
#     arr = list(map(int,list(format(num,'b'))))
#     f = [[[0 for k in range(2)] for j in range(2)] for i in range(len(arr))]
#     return dfs(0,True,f,arr,0,0)
# L,R =map(int,input().split())
# print(digitSearch(R)-digitSearch(L-1))

#75启动多任务排序
# relations = list(map(lambda s:s.split('->'),input().split()))
# def solution():
#     inDegree = {}
#     next = {}
#     for a,b in relations:
#         inDegree[b] = inDegree.get(b,0)
#         inDegree[a] = inDegree.get(a,0) + 1
#         next[b] = next.get(b,[])
#         next[b].append(a)
#         next[a] = next.get(a,[])
#
#     queue = []
#     for task in inDegree:
#         if inDegree[task] == 0:
#             queue.append(task)
#
#     ans = []
#     while len(queue) > 0:
#         queue.sort()
#         newQueue = []
#         for fa in queue:
#             ans.append(fa)
#             for ch in next[fa]:
#                 inDegree[ch] -= 1
#                 if inDegree[ch] == 0:
#                     newQueue.append(ch)
#         queue = newQueue
#
#     return ' '.join(ans)

#74最佳出牌方式
# cards = input()
# max_score = 0
# # 获取牌的最大得分
# def getMaxScore(card_count, unused_card_count, i, score):
#
#     global max_score
#
#     # 所有牌都打完了
#     if unused_card_count == 0:
#         # 则比较此时出牌策略获得的总分score，和历史最高分max_score，保留较大者
#         max_score = max(max_score, score)
#         return
#
#     # 没有可以出的牌，则继续递归到i+1开始出牌
#     if card_count[i] == 0:
#         getMaxScore(card_count, unused_card_count, i + 1, score);
#
#     # 还有可以出的牌，则从i开始出牌
#     # 如果当前牌的数量至少1张
#     if card_count[i] >= 1:
#         # 策略1、可以尝试出顺子，由于最大的顺子是9,10,J,Q,K,因此 i 作为顺子起始牌的话，不能超过9，且后续牌面 i+1, i+2, i+3, i+4 的数量都至少有1张
#         if i <= 9 and card_count[i + 1] >= 1 and card_count[i + 2] >= 1 and card_count[i + 3] >= 1 and card_count[
#             i + 4] >= 1:
#             card_count[i] -= 1
#             card_count[i + 1] -= 1
#             card_count[i + 2] -= 1
#             card_count[i + 3] -= 1
#             card_count[i + 4] -= 1
#             # 顺子是5张牌，因此出掉顺子后，可用牌数量减少5张，总分增加 (i + (i+1) + (i+2) + (i+3) + (i+4)) * 2
#             getMaxScore(card_count, unused_card_count - 5, i, score + (5 * i + 10) * 2)
#             # 回溯
#             card_count[i] += 1
#             card_count[i + 1] += 1
#             card_count[i + 2] += 1
#             card_count[i + 3] += 1
#             card_count[i + 4] += 1
#
#         # 策略2、出单张
#         card_count[i] -= 1
#         getMaxScore(card_count, unused_card_count - 1, i, score + i)
#         card_count[i] += 1
#
#     # 如果当前牌的数量至少2张，那么可以出对子
#     if card_count[i] >= 2:
#         card_count[i] -= 2
#         getMaxScore(card_count, unused_card_count - 2, i, score + i * 2 * 2)
#         card_count[i] += 2
#
#     # 如果当前牌的数量至少3张，那么可以出三张
#     if card_count[i] >= 3:
#         card_count[i] -= 3
#         getMaxScore(card_count, unused_card_count - 3, i, score + i * 3 * 2)
#         card_count[i] += 3
#
#     # 当前当前牌的数量至少4张，那么可以出炸弹
#     if card_count[i] >= 4:
#         card_count[i] -= 4
#         getMaxScore(card_count, unused_card_count - 4, i, score + i * 4 * 3)
#         card_count[i] += 4
#
#
# # 算法入口
# def solution():
#     # 数组索引是牌面分数, 数组元素是牌面数量, 其中 0 索引不用
#     card_count = [0] * 14
#
#     # 统计各种牌的数量
#     for card in cards:
#         # 1-9输入为数字1-9，10输入为数字0，JQK输入为大写字母JQK
#         # 1-9 牌面分数就是 1-9, 0的牌面分数是 10, J=11,Q=12,K=13, 可以发现牌面分数是连续的，可以和card_count数组的索引对应起来
#         if card == '0':
#             card_count[10] += 1
#         elif card == 'J':
#             card_count[11] += 1
#         elif card == 'Q':
#             card_count[12] += 1
#         elif card == 'K':
#             card_count[13] += 1
#         else:
#             i = ord(card) - ord('0')
#             card_count[i] += 1
#     getMaxScore(card_count, len(cards), 1, 0)
#     return max_score

#73删除目录后的ID序列
# def bfs(id):
#     queue = [id]
#     while len(queue) > 0:
#         fa = queue.pop(0)
#         if fa not in tree:
#             continue
#         for ch in tree[fa]:
#             if ch != remove:
#                 results.append(ch)
#                 queue.append(ch)
# #
# m = int(input())
# tree = {}
# for _ in range(m):
#     c,f = map(int,input().split())
#     tree.setdefault(f,[])
#     tree[f].append(c)
# results = []
# remove = int(input())
# if remove != 0:
#     bfs(0)
#
# results.sort()
# print(' '.join(map(str,results)))

#72部门人力分配
# m = int(input())
# requirements = list(map(int,input().split()))
# def check(limit):
#     l = 0
#     r = len(requirements) -1
#     need = 0
#     while l <= r:
#         if requirements[l] + requirements[r] <= limit:
#             l+=1
#         r-=1
#
#         need+=1
#     return m >= need
#
# def solution():
#     if len(requirements) == 1:
#         return requirements[0]
#     requirements.sort()
#     low = requirements[-1]
#     high = requirements[-2] + requirements[-1]
#     ans = high
#     while low <= high:
#         mid = (low+high) >> 2
#         if check(mid):
#             ans = mid
#             high = mid -1
#         else:
#             low = mid -1
#     return ans

#德州扑克
# def mapToNum(card):  # 牌大小映射位数值
#     if card == "J":
#         return 11
#     elif card == "Q":
#         return 12
#     elif card == "K":
#         return 13
#     elif card == "A":
#         return 14
#     else:
#         return int(card)
#
# def isFlush():
#     return len(colorSet) == 1  # 所有牌花色一样，即为同花#
#
# def isStraights():
#     lst = list(numCount.keys())
#
#     if len(lst) < 5:  # 顺子牌数不低于5张
#         return False
#
#     lst.sort(key=lambda x: mapToNum(x))  # 牌大小升序
#
#     # 除了2345A 顺子外，其余顺子的最大牌值 - 最小牌值 都为 4
#     return "2345A" == "".join(lst) or mapToNum(lst[-1]) - mapToNum(lst[0]) == 4
##
# def isFour():
#     return len(values) == 2 and values[0] == 4  # 四张相同数字 + 单张
##
# def isFullHouse():
#     return len(values) == 2 and values[0] == 3  # 三张相同数字 + 一对
##
# def isThree():
#     return len(values) == 3 and values[0] == 3  # 三张相同 + 两张单

# numCount = {}  # 统计各个牌大小的数量
# colorSet = set()  # 统计花色种类数量
#
# for _ in range(5):
#     num, color = input().split()
#
#     numCount.setdefault(num, 0)
#     numCount[num] += 1
#
#     colorSet.add(color)
#
# values = list(numCount.values())  # "各个牌大小"数量的集合
# values.sort(reverse=True)  # 数量降序
#
# ans = 0
#
# if isFlush() and isStraights():  # 同花顺
#     ans = 1
# elif isFour():  # 四条
#     ans = 2
# elif isFullHouse():  # 葫芦
#     ans = 3
# elif isFlush():  # 同花
#     ans = 4
# elif isStraights():  # 顺子
#     ans = 5
# elif isThree():  # 三条
#     ans = 6
# print(ans)

#70评论转换输出
# import sys
# sys.setrecursionlimit(10 ** 6)
# def dfs(level):
#     fa_name = queue.pop(0)
#     ch_size = int(queue.pop(0))
#     if len(tree) == level:
#         tree.append([])
#     tree[level].append(fa_name)
#     for _ in range(ch_size):
#         dfs(level+1)
#
# queue = input().split(',')
# tree = []
# while queue:
#     dfs(0)
# print(len(tree))
# for lst in tree:
#     print(' '.join(lst))

#69跳格子2
# nums = list(map(int,input().split()))
# def stealMoney(nums):
#     n = len(nums)
#     dp = [0] * n
#     if n >= 1:
#         dp[0] = nums[0]
#     if n >= 2:
#         dp[1] = max(nums[0],nums[1])
#     for i in range(2,n):
#         dp[i] = max(dp[i-1],dp[i-2]+nums[i])
#
#     return dp[n-1]
#
# def solution():
#     if len(nums) == 1:
#         return nums[0]
#     return max(stealMoney(nums[:-1]),stealMoney(nums[1:]))

#68会议接待
# def solution():
#     if bag == 0:
#         return 0
#     dp = [0] * (bag+1)
#     dp[0] = 1
#     for num in nums:
#         for j in range(bag,num-1,-1):
#             dp[j] = dp[j] + dp[j-num]
#     return dp[bag]
    # n = len(nums)
    # dp = [ [0] * (bag+1) for _ in range(n+1)]
    # dp[0][0] = 1
    # for i in range(1,n+1):
    #     num = nums[i-1]
    #     for j in range(bag+1):
    #         if j < num:
    #             dp[i][j] = dp[i-1][j]
    #         else:
    #             dp[i][j] = dp[i-1][j] + dp[i-1][j-num]
    # return dp[n][bag]
# try:
#     nums = list(map(int,input().split(',')))
#     bag = int(input())
#     print(solution())
# except:
#     print(0)

#67数值同化
# m,n = map(int,input().split())
# matrix = [list(map(int,input().split())) for _ in range(m)]
# matrix[0][0] = 1
# offsets = ((0,1),(0,-1),(1,0),(-1,0))
# count = 1
# queue = [[0,0]]
# while len(queue) > 0:
#     x,y = queue.pop(0)
#     for offset in offsets:
#         newX = x + offset[0]
#         newY = y + offset[1]
#     if m > newX >= 0 and n > newY >= 0 and matrix[newX][newY] == 0:
#         matrix[newX][newY] = 1
#         count +=1
#         queue.append([newX,newY])
# print(m*n-count)

#66数字游戏加减法
# s,t,a,b = map(int,input().split())
# x = 0
# diff = t - s
# def solution():
#     while True:
#         if (diff-a*x) % b == 0 or (diff + a*x) % b == 0:
#             return abs(x)
#         x+=1

#数组二叉树
# nums = list(map(int,input().split()))
# def isLeaf(index):
#     if nums[index] == -1:
#         return False
#     lc = index * 2 + 1
#     rc = index * 2 + 2
#     return(lc>=len(nums) or nums[lc]==-1) and (rc >= len(nums) or nums[rc] == -1)
# def solution():
#     minLeafIdx = len(nums)
#     minLeafVal = sys.maxsize
#     for i in range(len(nums)):
#         if isLeaf(i) and nums[i] < minLeafIdx:
#             minLeafIdx = i
#             minLeafVal = nums[i]
#     path = []
#     index = minLeafIdx
#     while True:
#         path.append(nums[index])
#         index -= 1
#         if index < 0:
#             break
#         index //= 2
#     path.reverse()
#     return  " ".join(map(str,path))

#64招聘
# class Group:
#     def __init__(self,l,r):
#         self.lastL = l
#         self.lastR = r
#         self.size = 1
# def group1():
#     ranges.sort(key = lambda x: x[0])
#     groups = []
#     for r in ranges:
#         flag = False
#         for g in groups:
#             if g.size < m and g.lastR <= r[0]:
#                 g.lastL = r[0]
#                 g.lastR = r[1]
#                 g.size += 1
#                 flag = True
#                 break
#         if not flag:
#             groups.append(Group(r[0],r[1]))
#     return len(groups)
#
# def group2():
#     ranges.sort(key=lambda x: -x[1])
#     groups = []
#     for r in ranges:
#         flag = False
#         for g in groups:
#             if g.size < m and g.lastL >= r[1]:
#                 g.lastL = r[0]
#                 g.lastR = r[1]
#                 g.size += 1
#                 flag = True
#                 break
#         if not flag:
#             groups.append(Group(r[0], r[1]))
#     return len(groups)
# m = int(input())
# n = int(input())
# ranges = [list(map(int,input().split())) for _ in range(n)]
# print(min(group1(),group2()))

#63查找有向网络头尾节点
# def solution():
#     n = int(input())
#     if n == 0:
#         print(-1)
#         return
#     tmp = list(map(int,input().split()))
#     #记录入度
#     inDegree = {}
#     #记录后继点集合
#     nxt = {}
#     #记录图中点
#     points  = set()
#     for i in range(0,2*n,2):
#         a = tmp[i]
#         b = tmp[i+1]
#         points.add(a)
#         points.add(b)
#         inDegree.setdefault(b,0)
#         inDegree[b] += 1
#         nxt.setdefault(a,[])
#         nxt[a].append(b)
#
#     total = len(points)
#     #记录图的头结点
#     head = 0
#     queue = []
#     for p in points:
#         if p not in inDegree:
#             heap = p
#             queue.append(p)
#             break
#     tails = []
#     count = 0
#     while len(queue) > 0:
#         fa = queue.pop(0)
#         count += 1
#
#         if fa not in nxt:
#             tails.append(fa)
#             continue
#         for ch in nxt[fa]:
#             inDegree[ch] -= 1
#             if inDegree[ch] == 0:
#                 queue.append(ch)
#     if count != total:
#         print(-1)
#     else:
#         tails.sort()
#         print(head,' '.join(map(str,tails)))

#62 数字序列比大小
# n = int(input())
# a = list(map(int,input().split()))
# b = list(map(int,input().split()))
# def solution():
#     a.sort()
#     b.sort()
#     la = 0
#     ra = n-1
#     lb = 0
#     rb = n-1
#     ans = 0
#     while la <= ra:
#         if a[ra] > b[ra]:
#             #田忌
#             ans+=1
#             ra -= 1
#             rb -= 1
#         elif a[ra] < b[rb]:
#             ans -= 1
#             la += 1
#             ra -= 1
#         else:
#             if a[la] > b[lb]:
#                 ans+= 1
#                 la += 1
#                 ra += 1
#             else:
#                 #
#                 if b[rb] > a[la]:
#                     ans -= 1
#                     la += 1
#                     rb -= 1
#     return ans

#61 组装最大可能性
# class Device:
#     def __init__(self,reliability,price):
#         self.reliability = reliability
#         self.price = price
# s,n = map(int,input().split())
# total = int(input())
# arr = [list(map(int,input().split())) for _ in range(total)]
#
# reliabilities = set()
# kinds = [[] for _ in range(n)]
# for ty,reliability,price in arr:
#     kinds[int(ty)].append(Device(reliability,price))
#     reliabilities.add(reliability)
#
# def binarySearch(kind,target):
#     low = 0
#     high =len(kind) - 1
#     while low <= high:
#         mid = (low+high) >> 1
#         device = kind[mid]
#         if device.reliability > target:
#             high = mid -1
#         elif device.reliability < target:
#             low = mid + 1
#         else:
#             return mid
#     return -low - 1
# def check(maxReliability):
#     sumPrice = 0
#     for kind in kinds:
#         idx = binarySearch(kind,maxReliability)
#         if idx < 0:
#             idx = -idx-1
#         if idx == len(kind):
#             return  False
#         sumPrice += kind[idx].price
#     return sumPrice <= s
# def solution():
#     ans = -1
#     for kind in kinds:
#         kind.sort(key = lambda x:(x.reliability,x.price))
#     maybe = list(reliabilities)
#     maybe.sort()
#     low = 0
#     high = len(maybe) - 1
#     while low <= high:
#         mid = (low+high) >> 1
#         if check(maybe[mid]):
#             ans = maybe[mid]
#             low = mid + 1
#         else:
#             high = mid - 1
#     return ans

#60矿堆寻宝
# 上下左右，四个方向的偏移量
# offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))
# # 广搜
# def bfs(i, j):
#     total = matrix[i][j]
#     matrix[i][j] = 0
#     queue = [[i, j]]
#     while queue:
#         x, y = queue.pop(0)
#         for offset in offsets:
#             newX = x + offset[0]
#             newY = y + offset[1]
#             if len(matrix) > newX >= 0 and len(matrix[0]) > newY >= 0 and matrix[newX][newY] > 0:
#                 total += matrix[newX][newY]
#                 matrix[newX][newY] = 0
#                 queue.append([newX, newY])
#     return total
#
# matrix = []
# while True:
#     try:
#         matrix.append(list(map(int, list(input()))))
#     except:
#         break
# maxWorth = 0
# for i in range(len(matrix)):
#     for j in range(len(matrix[i])):
#         if matrix[i][j] > 0:
#             maxWorth = max(maxWorth, bfs(i, j))
# print(maxWorth)

#59仿LISP算法
import math
# def calc(op,p1,p2):
#     if op == "add":
#         return p1 + p2
#     elif op == "sub":
#         return p1 - p2
#     elif op == "mul":
#         return p1 * p2
#     else:
#         return math.floor(p1/p2)
# def solution(s):
#     stack = []
#     sb = []
#     for c in s:
#         if (c== ')' or c == ' ') and len(sb) > 0:
#             stack.append(''.join(sb))
#             sb.clear()
#         if c == ')':
#             p2 = int(stack.pop())
#             p1 = int(stack.pop())
#             op = stack.pop()
#             stack.append(calc(op,p1,p2))
#         if c != ' ' and c != '(' and c != ')':
#             sb.append(c)
#     return stack.pop()
# s = input()
# try:
#     print(solution(s))
# except:
#     print('error')

#58wonderland
# costs = list(map(int,input().split()))
# days = list(map(int,input().split()))
# def solution():
#     maxDay = days[-1]
#     dp = [0] * (maxDay + 1)
#     index = 0
#     for i in range(1,maxDay+1):
#         if i == days[index]:
#             #买一日票
#             buy1 = dp[i-1] + costs[0]
#             buy3 = (dp[i-3] if i >= 3 else 0) + costs[1]
#             buy7 = (dp[i - 7] if i >= 7 else 0) + costs[2]
#             buy30 = (dp[i - 30] if i >= 30 else 0) + costs[3]
#             dp[i] = min(buy1,buy3,buy7,buy30)
#             index += 1
#         else:
#             dp[i] = dp[i-1]
#     return dp[maxDay]

#57书籍叠放算法
# books = eval(input())
# books.sort(key = lambda x:(x[0],-x[1]))
# nums = list(map(lambda x:x[1],books))
# def solution():
#     dp = [1] * len(nums)
#     #dp[i]以nums[i]结尾的最长递增子序列长度
#     for i in range(1,len(nums)):
#         for j in range(0,i):
#             if nums[i] > nums[j]:
#                 dp[i] = max(dp[i],dp[j]+1)
#     return max(dp)

#56最优资源分配
# m = int(input())
# n = int(input())
# seq = input()
# def solution():
#     boardCard = [m] * n
#     mapping = {'A':1,'B':2,"C":8}
#     for i in range(len(seq)):
#         need = mapping[seq[i]]
#         for j in range(n):
#             if boardCard[j] >= need:
#                 boardCard[j] -= need
#                 break
#     for remain in boardCard:
#         unUsed = int(remain)
#         used = m - unUsed
#         print('1' * used + '0' * unUsed)


#55 最少数量线段覆盖
# n = int(input())
# rans = [list(map(int,input().split(','))) for i in range(n)]
# def solution():
#     rans.sort(key=lambda  x: x[0])
#     stack = [rans[0]]
#     for i in range(1,n):
#         ran = rans[i]
#         while True:
#             if len(stack) == 0:
#                 stack.append(ran)
#                 break
#             s0,e0 = stack[-1]
#             s1,e1 = ran
#             if s1 <= s0:
#                 if e1 <= s0:
#                     break
#                 elif e1 < e0:
#                     break
#                 else:
#                     stack.pop()
#             elif s1 < e0:
#                 if e1 <= e0:
#                     break
#                 else:
#                     stack.append([e0,e1])
#                     break
#             else:
#                 stack.append(ran)
#                 break
#     return len(stack)

#54寻找最优的路测线路
# r = int(input())
# c = int(input())
# matrix = [list(map(int,input().split()))for _ in range(r)]
# dist = [0] * r * c
# dist[0] = matrix[0][0]
# pq = [0]
# offsets = ((0,1),(0,-1),(1,0),(-1,0))
# while len(pq) > 0:
#     u = pq.pop(0)
#     x = u // c
#     y = u % c
#     if x == r -1 and y == c - 1:
#         break
#     for offsetX,offsetY in offsets:
#         newX = x + offsetX
#         newY = y + offsetY
#         if newX < 0 or newX >= r or newY < 0 or newY >= c:
#             continue
#         v = newX * c + newY
#         w = min(dist[u],matrix[newX][newY])
#         if dist[v] < w:
#             dist[v] = w
#             pq.append(v)
#             pq.sort(key=lambda  i: dist[i])
# print(dist[r*c-1])

#53运输时间
# m,n = map(int,input().split())
# arrive = 0
# for i in range(m):
#     speed = int(input())
#     arrive = max(arrive,n/speed+1)
# cost= arrive-(m-1)

#52 战场索敌
# 输入获取
# n, m, k = map(int, input().split())  # 地图行数, 地图列数, 区域敌军人数上限值
# matrix = [input() for _ in range(n)]  # 地图矩阵
# visited = [[False for _ in range(m)] for _ in range(n)]  # 访问矩阵
# offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上、下、左、右偏移量
# def bfs(i,j):
#     count = 0
#     if matrix[i][j] == 'E':
#         count+= 1
#     visited[i][j] = True
#     queue = [(i,j)]
#     while len(queue) > 0:
#         x,y = queue.pop(0)
#         for offsetX,offsetY in offsets:
#             newX = x + offsetX
#             newY = y + offsetY
#             if n > newX >= 0 and m > newY >= 0 and not visited[newX][newY] and matrix[newX][newY] != '#':
#                 if  matrix[newX][newY] == 'E':
#                     count += 1
#                 visited[newX][newY] = True
#                 queue.append([newX,newY])
#     return count
# ans = 0
# for i in range(n):
#     for j in range(m):
#         if not visited[i][j] and matrix[i][j] != '#':
#             ans += 1 if bfs(i,j) < k else 0
# print(ans)


#51最佳对手
# n,d = map(int,input().split())
# arr = list(map(int,input().split()))
# def recursive(lst,index,canAbandon,sumV):
#     if index >= len(lst):
#         return sumV
#     minSum = float('inf')
#     minSum = min(minSum,recursive(lst,index+2,canAbandon,sumV+lst[index]))
#     if canAbandon:
#         minSum = min(minSum,recursive(lst,index+1,False,sumV))
#     return minSum
# def solution():
#     arr.sort()
#     segments = []
#     segment = []
#     for i in range(1,n):
#         diff = arr[i] - arr[i-1]
#         if diff <= d:
#             segment.append(diff)
#         elif len(segment) > 0:
#             segments.append(segment)
#             segment = []
#     if len(segment) > 0:
#         segments.append(segment)
#     if len(segments) == 0:
#         return -1
#     else:
#         return sum(map(lambda lst:recursive(lst,0,len(lst) % 2 == 0, 0),segments))

#51 5G网络建设
# class UnionFindSet:
#     def __init__(self,n):
#         self.fa = [i for i in range(n)]
#         self.count = n
#     def find(self,x):
#         if x!= self.fa[x]:
#             self.fa[x] = self.find(self.fa[x])
#             return self.fa[x]
#         return x
#     def union(self,x,y):
#         x_fa = self.find(x)
#         y_fa = self.find(y)
#         if x_fa != y_fa:
#             self.fa[y_fa] = x_fa
#             self.count -= 1
# n = int(input())
# m = int(input())
# edges = []
# for _ in range(m):
#     x,y,z,p = map(int,input().split())
#     if p == 0:
#         edges.append([x,y,z])
#     else:
#         edges.append([x,y,0])
# def kruskal():
#     minWeight = 0
#     edges.sort(key=lambda x:x[2])
#     ufs = UnionFindSet(n+1)
#     for x,y,x in edges:
#         if ufs.find(x) != ufs.find(y):
#             minWeight += z
#             ufs.union(x,y)
#             if ufs.count == 2:
#                 return  minWeight
#     return -1

#83文件缓存系统
# 双向链表节点
class Node:
    def __init__(self, key, val, freq):
        """
        :param key: 记录本题的键
        :param val: 记录本题的值
        :param freq: 记录该键被访问的次数
        """
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = None
        self.next = None


# 双向链表
class Link:
    def __init__(self):
        self.size = 0
        self.head = None
        self.tail = None

    def addLast(self, node):
        """
        尾插
        :param node: 要被插入的节点
        """
        if self.size == 0:
            # 空链表，则node节点插入后，即为头、尾节点
            self.head = node
            self.tail = node
        else:
            # 非空链表，则node节点插入到tail节点后面
            self.tail.next = node
            node.prev = self.tail
            self.tail = node

        self.size += 1

    def remove(self, node):
        """
        删除指定节点
        :param node: 要删除的节点
        """
        if self.size == 0:
            # 空链表没有节点，所以无法删除
            return

        if self.size == 1:
            # 链表只有一个节点，则删除完后，变为空链表
            self.head = None
            self.tail = None
        elif self.head == node:
            # 如果要删除的节点是头节点
            self.head = self.head.next
            self.head.prev = None
        elif self.tail == node:
            # 如果要删除的节点是尾节点
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            # 如果要删除的节点是中间节点
            node.prev.next = node.next
            node.next.prev = node.prev

        self.size -= 1


# LFU缓存
class LFUCache:
    def __init__(self, capacity):
        self.keyMap = {}  # keyMap用于记录key对应的node
        self.freqMap = {}  # freqMap的key是访问次数，value是具有相同访问次数的key对应的node组成的链表，链表头是最远访问的，链表尾是最近访问的
        self.capacity = capacity  # LFU缓存中能记录的最多key的数量
        self.minFreq = 0  # LFU缓存中所有的key中最少的访问次数

    def get(self, key):
        # 如果文件不存在，则不作任何操作。
        if key not in self.keyMap:
            return

        # 每次文件访问后，总访问次数加1，最近访问时间更新到最新时间
        node = self.keyMap[key]
        self.incNodeFreq(node)

    def put(self, key, val):
        # 如果新文件的文件名和文件缓存中已有的文件名相同，则不会放在缓存中
        if key in self.keyMap:
            return

        # 当缓存空间不足以存放新的文件时，根据规则删除文件，直到剩余空间满足新的文件大小位置，再存放新文件。
        while self.capacity < val:
            if self.minFreq == 0:
                # 文件系统空了，也放不下该文件，则不放入
                return

            # 找出最少访问次数对应的链表
            minFreqLink = self.freqMap[self.minFreq]

            # 链表头部节点是最少访问次数中，最远访问的文件，我们需要删除它
            removeNode = minFreqLink.head
            # 删除对应文件后，文件系统容量新增
            self.capacity += removeNode.val

            # 执行删除操作，freqMap和keyMap都要删除掉对应文件的记录
            minFreqLink.remove(removeNode)
            self.keyMap.pop(removeNode.key)

            # 如果删除后，最少访问次数的链表空了，则需要找到下一个最少访问次数的链表
            if minFreqLink.size == 0:
                # 最少次数的链表空了，则删除对应最少次数的记录
                del self.freqMap[self.minFreq]

                # 更新最少次数
                if len(self.freqMap.keys()) > 0:
                    self.minFreq = min(self.freqMap.keys())
                else:
                    # 文件系统没有缓存文件了，则最少次数为0，表示文件系统空了
                    self.minFreq = 0

        # 新增文件，则文件系统容量减少
        self.capacity -= val
        # 新增文件的访问次数为1，因此最少访问次数变为了1
        self.minFreq = 1
        node = Node(key, val, self.minFreq)
        # 执行新增操作，freqMap和keyMap都要新增对应文件的记录
        self.freqMap.setdefault(self.minFreq, Link())
        self.freqMap.get(self.minFreq).addLast(node)
        self.keyMap[key] = node

    def incNodeFreq(self, node):
        """
        增加key的访问次数
        :param node: key对应的node
        """
        # 由于key的访问次数增加，因此要从原访问次数的链表中删除
        self.freqMap[node.freq].remove(node)

        # 如果原链表删除当前key对应的节点后为空，且原链表对应的访问次数就是最少访问次数
        if self.freqMap[node.freq].size == 0:
            # 最少次数的链表空了，则删除对应最少次数的记录
            del self.freqMap[node.freq]

            # 则最少访问次数对应的key没有了，因此最少访问次数++（即当前key访问次数++后，当前key的访问次数还是最少访问次数）
            if node.freq == self.minFreq:
                self.minFreq += 1

        # 当前key访问次数++
        node.freq += 1

        # 将当前key对应的node转移到对应增加后的访问次数对应的链表尾部（最近访问）
        self.freqMap.setdefault(node.freq, Link())
        self.freqMap[node.freq].addLast(node)


# 输入获取
m = int(input())

lfu = LFUCache(m)

n = int(input())

for _ in range(n):
    operation = input().split()

    op = operation[0]
    fileName = operation[1]

    if "put" == op:
        fileSize = int(operation[2])
        lfu.put(fileName, fileSize)
    else:
        lfu.get(fileName)

if lfu.capacity == m:
    print("NONE")
else:
    ans = list(lfu.keyMap.keys())
    ans.sort()
    print(",".join(ans))